from timeit import timeit 
def Erato3(end=3): #最佳做法
    
    if end<3:
        if end==2:
            return [2]
        return None
    
    isPrime=[True]*end

    for i in range(3,int(end**0.5)+1,2): ## 指定步长参数，进行列表切片赋值
        if isPrime[i]: #去除此判断会导致重复更改，当i==9时，仍进行修改。 不影响答案，但影响时间。
            isPrime[i * i::2 * i] = [False] * ((end - i * i - 1) // (2 * i) + 1) 
        # isPrime[i * i::2 * i] = [False]*len(isPrime[i * i::2 * i]) #效果等价于上一句

    return [2]+[i for i in range(3,end,2) if isPrime[i]]

# num=int(input('输入一个整数：'))
 
def divPrime(num:int): # 最易懂
    res=[]
    d=2
    while num>1:
        while num%d==0:
            res.append(d)
            num//=d
        d+=1
    
    return res


def divPrime2(num): # 最优解法
    res=[]
    while True:
        for i in range(2,num+1):   #range函数左取右不取，从2检索到n..num+1
            b=num%i                #计算余数
            if b ==0:            #条件判断，如果余数是0，i就是n的一个素因数
                res.append(i)  #将这个素因数放进列表
                num=num//i           #将n的值除以这个素因数，即将这个素因数去掉
                break            #结束循环，进入下一轮while循环
        else:
            break                #若for in 循环没有执行break，即n的素因数已经取完，则结束while循环
    
    return res


def divPrime3(num):
    res=[]
    prime=Erato3(int(num**0.5))
    for i in prime:
        if num==1:
            return res
        while num%i==0:
            res.append(i)
            num//=i
    return res

def divPrime_factor(number):
  #递归终止条件
  if number == 1:
    return []
  else:
    for i in range(2,number+1):
      #得到商和余
      n,d = divmod(number,i)
      if d == 0:
        return [i] + divPrime_factor(n)

def clock():
    t=timeit(stmt="divPrime(97532468)",setup="from divPrime import divPrime",number=1000) 
    t2=timeit(stmt="divPrime2(97532468)",setup="from divPrime import divPrime2",number=1000) 
    t3=timeit(stmt="divPrime3(97532468)",setup="from divPrime import divPrime3",number=1000) 
    t4=timeit(stmt="divPrime_factor(97532468)",setup="from divPrime import divPrime_factor",number=1000) 

    print(t,t2,t3,t4,sep="\n")
# 0.14454905800812412
# 0.11338614599662833
# 0.31627874801051803
# 0.23998509299417492

if __name__=="__main__":
    clock()

    num=180 #97532468 #16675561080 #
    res=divPrime_factor(num)
    print(*res,sep='*')

